Constructing an adjacency list from a simple list of edges.

  • This function converts an edge list, which is easy to store, into an adjacency list for efficient neighbor lookups.
  • We start by initializing a dictionary where each vertex maps to an empty set. This pre-allocates an entry for every vertex.
  • The core logic iterates through each edge (u, v) and adds the connection in both directions to ensure symmetry, a key property of undirected graphs.
Python: build_adj_undirected
def build_adj_undirected(V, edges):
    adj = {v:set() for v in V}
    for u,v in edges:
        adj[u].add(v); adj[v].add(u)
    return adj

V = ["A","B","C","D"]
edges = [("A","B"),("A","C"),("B","D")]
build_adj_undirected(V, edges)